import java.util.Arrays;

//旋转数组问题
//class Solution {
//    public void rotate(int[] nums, int k) {
//        int n = nums.length;
//        int t = 0;
//        for (int i = 0; i < k; i++) {
//            for (int j = 0; j < n - 1; j++) {
//                if (j == n - 2){
//                    t = nums[j + 1];
//                    nums[j + 1] = nums[j];
//                    nums[0] = t;
//                }else {
//                    t = nums[j + 1];
//                    nums[j + 1] = nums[j];
//                    nums[j + 2] = t;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(nums));
//    }
//}以上为错误的想法
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // 处理k大于数组长度的情况
        reverse(nums, 0, n - 1); // 反转整个数组
        reverse(nums, 0, k - 1); // 反转前k个元素
        reverse(nums, k, n - 1); // 反转剩余的元素
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

class Solution1 {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = 0;
        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}